1. Field of the Invention
The present invention relates to a message relaying scheme that is suitable for constructing a ultra-high-speed message relaying system.
2. Description of the Background Art
In recent years, in conjunction with the explosive spread of the so called Internet, the throughput improvement in a connection-less network for leading the so called IP message to a desired terminal has become a major technical problem.
In the case of connection-less network, the end-to-end communications are provided as each routing processing device refers to a destination address assigned to each individual message and transfers the individual message independently to a desired output path. For this reason, it is possible to utilize the bandwidth of each physical link more flexibly compared with the connection-oriented network, and there is an advantage in that the bandwidth of the physical link can be utilized efficiently in a situation where traffics transmitted by terminals are highly bursty, which is characteristic of applications such as WWW for which the spontaneity in the continuous information communications has low importance.
On the other hand, there is a problem in that the amount of calculations required to the routing processing device at a time of routing individual message is overwhelmingly large compared with the connection-oriented network so that it is difficult to realize a high throughput routing processing device.
This problem stems both from the large amount of calculations that is inherently associated with the connection-less communications due to the fact that a physical link to which each message should be outputted must be determined whenever a message arrives, and from the physical constraint associated with electric circuits that it is very difficult to construct ultra-high-speed signal transmission paths using electric signals. This problem becomes particularly noticeable in the case where the physical link accommodated by the routing processing device uses various protocols such as Ethernet, PPP, ATM and SDH, or in the case of providing the so called multicast connection in which a single message is to be copied and lead to plural output paths.
A conventionally adopted method for resolving this problem is one in which a plurality of routing processing devices are directly connected by a physical link group and operated such that they can be regarded as a single routing processing device as a whole, as shown in FIG. 57.
In outline, the ultra-high-speed message relaying system shown in FIG. 57 operates as follows. When a message is entered from a connection-less network 103-i to a routing processing device 102-i, the routing processing device 102-i extracts a destination address of the entered message, obtains a next hop address of that message by referring to a routing table which has the extracted destination address as a key, selects a physical link corresponding to that next hop address from physical links connected to the own device, and transmits the message toward that physical link. When this operation is carried out by every routing processing device 102-i, the message transfer between connection-less networks 103-i via a plurality of routing processing devices 102-i can be realized. At this point, the routing processing at each routing processing device 102-i is carried out independently from any other routing processing device 102-j so that the throughput of the routing processing for the system as a whole can be improved.
However, this scheme directly arranges the physical links among the routing processing devices 102-i so that the bandwidth of the communication path between each connected routing processing devices 102-i becomes fixed and the transmission bandwidth allocation between the routing processing devices cannot follow the dynamic change of traffics among the connection-less networks. For this reason, this scheme has a problem that it is impossible to utilize the bandwidth of the physical link efficiently.
In particular, in the case of applications such as WWW in which the user""s access target changes frequently, messages transmitted from one routing processing device 102-i are not uniformly distributed over other connection-less networks so that the bandwidth required between the routing processing devices 102-i and 102-j changes largely in time, but this scheme cannot provide the required bandwidth between the routing processing devices 102-i and 102-j in such a situation. Consequently, this scheme has a problem that the comfortable communications cannot be provided to users because a length of a queue for holding messages to be transmitted to a physical link with insufficient bandwidth that is connected to a connection-less network 103-i becomes long so that the message delay time becomes extremely long.
As described, the conventional routing processing device has been associated with a problem that it is difficult to realize a high throughput routing processing device because of the large amount of calculations that is inherently associated with the connection-less communications and the physical constraint associated with electric circuits. This problem becomes particularly noticeable in the case where the routing processing device accommodates various protocols or in the case of providing the multicast connection.
In addition, the conventional ultra-high-speed message relaying system formed by combining the routing processing devices, the transmission bandwidth allocation between the routing processing devices is fixed so that the bandwidth cannot be allocated by following the traffic pattern that continually changes in time, and therefore there has been a problem that the comfortable communications cannot be provided to users.
It is therefore an object of the present invention to provide a message relaying scheme suitable for constructing a ultra-high-speed message relaying system, which is capable of allocating the bandwidth by following the traffic pattern between the routing processing devices that are continually changing in time and transferred by various protocols.
It is another object of the present invention to provide a message relaying scheme capable of providing the multicast connection by resolving the problem due to the large amount of calculations that is inherently associated with the connection-less communications and the physical constraint associated with electric circuits.
According to one aspect of the present invention there is provided a message relay device connected with a plurality of routing processing devices for carrying out connection-less communications, for relaying a message from one routing processing device to another routing processing device, the message relay device comprising: a plurality of interface units provided in correspondence to the routing processing devices; a switching unit connecting the plurality of interface units; and a command unit for commanding the switching unit to set up a bypass communication channel corresponding to an internal identifier which is an identifier defined within the message relay device for identifying at least a target interface unit corresponding to a relaying target routing processing device of each message; wherein each interface unit determines a flow to which an input message entered from a corresponding routing processing device of each interface unit belongs and assigns the internal identifier to the input message according to the flow, transmits the input message to the switching unit, and receives an output message to be outputted to the corresponding routing processing device of each interface unit from the switching unit; and the switching unit sets up the bypass communication channel according to the internal identifier in response to a command from the command unit, and switches messages transmitted from one interface unit to another interface unit using the bypass communication channel.
In this aspect of the present invention, the command unit can be contained in each interface unit so that a set up of the bypass communication channel is commanded from each interface unit to the switching unit.
According to this aspect of the present invention, a plurality of routing processing devices for carrying out connection-less communications are connected not directly by physical links but by this message relay device. Then, at this message relay device, when a message is entered from one routing processing device, the corresponding interface unit determines a flow to which this message belongs (the flow specifies at least a relaying target routing processing device of that message), and assigns an internal identifier according to this flow to the message.
Also, each interface unit commands the setting up of the bypass communication channel that can be set in correspondence to the internal identifier to the switching unit. At the switching unit, the bypass communication channel is set up according to a command from the interface unit, and the switching in units of flows (according to the internal identifier indicating the flow to which the message belongs) is carried out using this bypass communication channel, rather than transferring each message by analyzing its content.
Consequently, the large amount of calculations that is inherently associated with the connection-less communications can be absorbed by the interface units that are provided distributedly, and the transmission bandwidth allocation among the routing processing devices can be made to follow the dynamic traffic change.
Also, in this aspect of the present invention, the switching unit may also transfer messages transmitted from one interface unit to another interface unit using a default communication channel that is set up in advance, and each interface unit may judge whether each arrived message arriving from the default communication channel is a message to be received by this interface unit or not by referring to each arrived message, and receive each arrived message when it is Judged as a message to be received by this interface unit.
In this way, the switching unit can have a default communication channel for unspecified correspondents in addition to the bypass communication channel that is set up by specifying a correspondent, so that the transfer to appropriate routing processing device becomes possible even for a message that belongs to a flow for which the bypass communication channel is not set up.
For example, in the case of protocol such as Ethernet in which the destination is specified by the layer 2 address, messages to which the internal identifier is not assigned can be transferred by broadcasting through the default channel, and filtering at the receiving side using the destination MAC address or the like. Also, in the case of protocol such as PPP in which the destination is not specified by the layer 2 address, messages assigned with the internal identifier that contains information indicating the destination interface unit can be transferred by point-to-point transmission (in which the receiving side receives messages assigned with the internal identifier that contains own unit as the destination information) through the default channel.
Also, in this aspect of the present invention, each interface unit may obtain the internal identifier by checking a content of a prescribed region within a received message that is entered from the corresponding routing processing device of each interface unit and to be outputted to the default communication and/or an input port from which the received message is entered, and command the switching unit to set up the bypass communication channel toward a target interface unit corresponding to a relaying target routing processing device of the received message that is to be set in correspondence to the internal identifier, when a prescribed condition is satisfied, and each interface unit may transmit a new message entered from the corresponding routing processing device of each interface unit to the bypass communication channel when the internal identifier that is assigned to the new message as a result of checking the content of the prescribed region within the new message and/or the input port from which the new message is entered, is set in correspondence to the bypass communication channel.
In this way, the bypass communication channel set up can be triggered by a message transmitted to the default communication channel in a state where the bypass communication channel capable of transmitting the entered message is not set up, and this bypass channel can be used thereafter.
Also, in this aspect of the present invention, each interface unit may have a plurality of message buffers that can be set in correspondence to different internal identifiers, and each interface unit may allocate one message buffer to a received message entered from the corresponding routing processing device of each interface unit and temporarily store the received message in said one message buffer at a time of assigning the internal identifier to the received message if no message buffer is already set in correspondence to the internal identifier to be assigned to the received message, and transmit each message read out from each message buffer either to the bypass communication channel or the default communication channel which is selected according to a prescribed condition.
Also, in this aspect of the present invention, each interface unit may command a set up of the bypass communication channel toward a target interface unit corresponding to a relaying target routing processing device of each message that has a possibility of being entered from the corresponding routing processing device of each interface unit, as a communication channel to be set in correspondence to the internal identifier that is obtained from a content of a prescribed region within each message and/or an input port from which each message is expected to be entered, and each interface unit may transmit a received message entered from the corresponding routing processing device of each interface unit to the bypass communication channel when the internal identifier that is assigned to the received message as a result of checking the content of the prescribed region within the received message and/or the input port from which the received message is entered, is set in correspondence to the bypass communication channel.
In this way, the bypass communication channel capable of transmitting a message can be set up before that message is entered, and this bypass channel can be used immediately when this message is actually entered.
Also, in this aspect of the present invention, the message relay device may further comprise a layer 3 processing unit connected with each interface unit, which analyzes each message including information of layer 3 and/or upper layers that is entered from a certain routing processing device into a corresponding interface unit, determines a flow to which messages to be assigned with the internal identifier belong, and commands each interface unit to assign the internal identifier when a message belonging to the flow is entered, and the command unit may be contained in the layer 3 processing unit so that a set up of the bypass communication channel is commanded from the layer 3 processing unit to the switching unit.
Instead of the above described case where each interface unit commands the bypass communication channel set up to the switching unit, it is also possible to provide the layer 3 processing unit that commands the bypass communication channel set up to the switching unit. In this way, when each interface unit does not have the layer 3 termination function, it becomes possible to set up the bypass channel for the flow automatically in finer granularity based on the flow analysis accounting for the information of layer 3 and/or upper layers.
Also, in this aspect of the present invention, the layer 3 processing unit may analyze those messages which are control protocol messages for notifying in advance a flow to which messages that have possibilities of being entered from the certain routing processing device into the corresponding interface unit belong.
In this way, it becomes possible to set up the bypass communication channel toward the correspondent interface unit that is to be used by the interface unit at a time of transmitting entered messages to the switching unit, before messages to be relayed are actually entered into this message relay device.
Also, in this aspect of the present invention, the layer 3 processing unit may refer to a content of each message entered from the certain routing processing device into the corresponding interface unit, and transfer each message to the target interface unit corresponding to the relaying target routing processing device of each message using the default communication channel, and the layer 3 processing unit may analyze those messages which are transmitted using the default communication channel.
In this way, the interface unit can transfer the entered message using the default communication channel through the layer 3 processing unit while in a state where the bypass communication channel capable of transmitting the entered message is not set up, and a message transferred in such a way can trigger the bypass communication channel set up so that this bypass channel can be used thereafter.
Also, in this aspect of the present invention, each interface unit may assign the internal identifier to each message entered from the corresponding routing processing device of each interface unit by referring to at least a layer 2 destination address information within each message, where the relaying target routing processing device is identified according to the layer 2 destination address information.
Also, in this aspect of the present invention, each interface unit may assign the internal identifier to each message entered from the corresponding routing processing device of each interface unit by referring to at least a layer 2 header information within each message, where the relaying target routing processing device is identified according a relationship between the layer 2 header information and its relaying target routing processing device which is stored in advance.
Also, in this aspect of the present invention, each interface unit may assign the internal identifier to each message entered from the corresponding routing processing device of each interface unit by referring to information of layer 3, or layer 3 and upper layers, within each message.
Also, in this aspect of the present invention, each interface unit may assign the internal identifier to each message entered from the corresponding routing processing device of each interface unit by referring to at least an information capable of identifying a flow to which each message was regarded as belonging at the corresponding routing processing device, which is written in a specific region within each message, where the relaying target routing processing device is identified from a relationship between the flow and its relaying target routing processing device which is stored in advance.
Also, in this aspect of the present invention, each interface unit and the corresponding routing processing device of each interface unit may be connected by a plurality of physical links or logical paths, and each interface unit may assign the internal identifier to each message entered from the corresponding routing processing device of each interface unit by checking at least a physical link or logical path from which each message is entered, where the relaying target routing processing device is identified according to a relationship between an information regarding the physical link or logical path from which each message is entered and its relaying target routing processing device which is stored in advance.
Also, in this aspect of the present invention, each interface unit and the corresponding routing processing device of each interface unit may be connected by a plurality of physical links or logical paths, and each interface unit may notify an internal identifier information indicating the internal identifier and a type of messages to which the internal identifier will be assigned, to the target interface unit corresponding to the relaying target routing processing device, and attach the internal identifier to each message that is transmitted to the switching unit using the bypass communication channel, and the target interface unit corresponding to the relaying target routing processing device may select a physical link or logical path to be used in outputting each message to the relaying target routing processing device according to the internal identifier information notified for the internal identifier attached to each message received from the bypass communication channel.
Also, in this aspect of the present invention, the internal identifier may be obtained from an information on a content of a prescribed region within each message and/or an input port from which each message is entered, by compressing its information amount to a fixed length.
Namely, the internal identifier of the present invention can be given a role of the intermediary for establishing a mapping between an information for defining the flow to which the message belongs (an information on a content of a prescribed region within the message and/or an input port from which the message is entered) and an information for determining a route at a time of switching the message on the communication channel (destination MAC address, VPI/VCI of ATM, optical wavelength, etc.). At this point, if the internal identifier is formed in a fixed length by compressing the information amount of the flow definition information, even in the case where routing processing devices uses different protocols or different flow definitions, it becomes possible to realize the flow identification within this message relay device in a unified manner using a shorter fixed length information so that it is more convenient.
Note however that the internal identifier of the present invention may be the flow definition information itself, or the information for determining the switching route itself. It is also possible to use a configuration in which the switching unit can determine the switching route of the message from the internal identifier which is valid within this message relay device (such as a configuration in which the internal identifier of a special kind becomes the information for determining the switching route itself).
Also, in this aspect of the present invention, the switching unit may be formed by optical communication paths capable of realizing wavelength division multiplexed burst switching, in which the bypass communication channel is formed according to an optical wavelength, and each interface unit may allocate an optical wavelength to each message entered from the corresponding routing processing device of each interface unit according to the internal identifier, and transmit each message to the switching unit using the optical wavelength allocated to each message.
In this way, by allocating a wavelength according to the internal identifier (the wavelength to be allocated may be determined by a prescribed algorithm according to the internal identifier or the internal identifier itself may indicate the wavelength directly) and realizing the switching using the optical signals as medium, it is also possible to resolve the physical constraint associated with electric circuits, and the throughput of the connection-less network can be improved.
Also, in this aspect of the present invention, each interface unit may have a buffer memory for storing each message in a region provided in correspondence to the internal identifier, and allocate the optical wavelength to the internal identifier when each message stored in the buffer memory satisfies a prescribed condition.
In this way, by allocating the optical wavelength to be used as the communication channel dynamically by using the internal identifier (to which a buffer corresponds) as the intermediary (as in the case where messages to be relayed are actually stored in excess of a prescribed amount, for example) the wavelength resources in this message relay device can be utilized efficiently.
Also, in this aspect of the present invention, each interface unit may select one of a plurality of optical wavelengths, that are allocated in advance as optical wavelengths to be uniquely received by the target interface unit corresponding to the relaying target routing processing device, which is currently not used by other interface units, and transmit each message using said one of the plurality of optical wavelengths.
In this way, by making the transmission wavelength variable (selected at each occasion) while fixing the reception wavelength, it becomes sufficient for each interface unit to receive only the prescribed wavelength so that a configuration of the optical reception unit can be simplified. Here, the fact that the transmission wavelength that is intended to be used from now is not used by the other interface units is checked (by circulating a negotiation message on the ring, for example), so that the switching unit can have a buffer-less configuration.
Also, in this aspect of the present invention, when there are a plurality of relaying target routing processing devices for a certain message, an interface unit which is a source of the certain message may notify to one interface unit corresponding to one relaying target, one optical wavelength selected for said one interface unit and information on other relaying targets, and transmit the certain message using said one optical wavelength, and said one interface unit may transmit a message obtained by copying the certain message received at said one optical wavelength, by using another optical wavelength selected for another interface unit corresponding to one of the other relaying targets.
In this way, it becomes possible to realize the multicast using the bypass communication channel in the case where the reception wavelength is fixed.
Also, in this aspect of the present invention, each interface unit may notify the target interface unit corresponding to the relaying target routing processing device to uniquely receive one optical wavelength among those optical wavelengths for which no collision with other interface units occur, and transmit each message using said one optical wavelength.
In this way, by making both the transmission wavelength and the reception wavelength variable (selected at each occasion), the wavelength resources in this message relay device can be utilized more efficiently. Here, the fact that the transmission wavelength that is intended to be used from now is not causing any collision with the other interface units is checked (by circulating a negotiation message on the ring, for example), so that the switching unit can have a buffer-less configuration.
Also, in this aspect of the present invention, each interface unit may judge an optical wavelength which is currently not used in optical communication paths between each interface unit and the target interface unit corresponding to the relaying target routing processing device, as one of those optical wavelength for which no collision with other interface units occur.
Namely, in the case of making both the transmission wavelength and the reception wavelength variable, the reutilization of the wavelength becomes possible in this way (the identical wavelength can be used in both an optical communication path from a transmitting interface A to a receiving interface B and an optical communication path from a transmitting interface C to a receiving interface D provided that there is no overlap).
Also, in this aspect of the present invention, when there are a plurality of relaying target routing processing devices for a certain message, a certain interface unit which is a source of the certain message may notify information on other relaying targets at a time of notifying a certain another interface unit corresponding to one relaying target to uniquely receive said one optical wavelength among those optical wavelengths for which no collision with other interface units occur, said certain another interface unit may notify some other interface unit corresponding to one of the other relaying targets to uniquely receive another optical wavelength among those optical wavelengths for which no collision with other interface units occur, and upon receiving the certain message from the certain interface unit at said one optical wavelength notified from the certain interface unit, said certain another interface unit may transmit a message obtained by copying the certain message, by using said another optical wavelength notified to said some other interface unit corresponding to one of the other relaying targets.
In this way, it becomes possible to realize the multicast using the bypass communication channel in the case where the reception wavelength is also variable.
According to another aspect of the present invention there is provided a message relay device connected with a plurality of routing processing devices for carrying out connection-less communications, for relaying a message from one routing processing device to another routing processing device, the message relay device comprising: a plurality of interface units provided in correspondence to the routing processing devices; and a switching unit connecting the plurality of interface units; wherein each interface unit checks an input message entered from a corresponding routing processing device of each interface unit according to a protocol used in the input message, and assigns to the input message an internal identifier which is an identifier defined within the message relay device for identifying at least a target interface unit corresponding to a relaying target routing processing device of the input message, has a buffer for storing the input message until a bypass communication channel from each interface unit toward another interface unit which is capable of transmitting messages assigned with the internal identifier becomes available at the switching unit, transmits the input message stored in the buffer to the switching unit while maintaining a protocol format of the input message as entered, and receives an output message to be outputted to the corresponding routing processing device of each interface unit from the switching unit; and the switching unit switches messages transmitted from one interface unit to another interface unit using the bypass communication channel.
Here, in order to make it possible to accommodate the routing processing devices using different protocols in this message relay device, a processing sensitive to the protocol, that is, a portion for mapping the flow and the internal identifier, is provided in each interface unit, and the message buffering function is provided at this mapping processing side (the switching processing side is made in a buffer-less configuration).
In this way, the interior of the mapping processing portion can carry out the switching using the internal identifier or the communication channel set in correspondence to the internal identifier without becoming conscious of the protocol (by maintaining the protocol format of each message).
According to another aspect of the present invention there is provided a message relay device connected with a plurality of routing processing devices for carrying out connection-less communications, for relaying a message from one routing processing device to another routing processing device, the message relay device comprising: a plurality of interface units provided in correspondence to the routing processing devices; and a switching unit connecting the plurality of interface units using optical rings capable of transmitting optical signals in a plurality of wavelengths by multiplexing the optical signals; wherein each interface unit transmits an input message entered from a corresponding routing processing device of each interface unit, through a communication channel toward a target interface corresponding to a relaying target routing processing device of the input message which is formed by using a wavelength determined according to the input message, receives an output message to be outputted to the corresponding routing processing device of each interface unit from the switching unit by selectively intercepting a wavelength uniquely allocated to each interface unit, and processes an intercepted message intercepted by selectively intercepting a wavelength commonly allocated to the plurality of interface units, according to information indicating an interface unit which is a destination of the intercepted message.
Here, the bypass communication channel is formed and the switching in units of flows is realized using optical signals as medium by using optical rings and allocating a wavelength uniquely to each interface unit. Also, the default communication channel is formed by using a prescribed wavelength that is to be intercepted by every interface unit, and each interface unit checks the intercepted message and carries out the processing such as transmitting the message to a neighboring interface unit (point-to-point with a unit other than own unit as the destination), receiving the message (point-to-point with own unit as the destination), receiving the message while transmitting the message to a neighboring interface unit as well (broadcast or multicast), or receiving the message and analyzing a content of the message in order to transmit it to a neighboring interface by rewriting the content if necessary (ring circulation).
According to another aspect of the present invention there is provided a message relay device connected with a plurality of routing processing devices for carrying out connection-less communications, for relaying a message from one routing processing device to another routing processing device, the message relay device comprising: a plurality of interface units provided in correspondence to the routing processing devices; and a switching unit connecting the plurality of interface units using optical rings capable of transmitting optical signals in a plurality of wavelengths by multiplexing the optical signals; wherein each interface unit transmits an input message entered from a corresponding routing processing device of each interface unit, through a communication channel toward a target interface corresponding to a relaying target routing processing device of the input message which is formed by using a wavelength determined according to the input message, and receives an output message to be outputted to the corresponding routing processing device of each interface unit from the switching unit by selectively intercepting a wavelength uniquely allocated to each interface unit, where a number of wavelengths that can be received at each interface unit is set to be greater than a number of wavelengths that can be transmitted from each interface unit.
Here, the bypass communication channels at each interface unit have the reception capacity that is greater than the transmission capacity so that a possibility for having a collision occurring within the switching unit using the optical rings can be lowered.
According to another aspect of the present invention there is provided a message relay method for relaying a message from one routing processing device to another routing processing device among a plurality of routing processing devices for carrying out connection-less communications, the method comprising the steps of: determining a flow to which each message entered from one routing processing device belongs, according to a prescribed condition, by referring to a content of each message; allocating a message buffer to the flow and storing each message into the message buffer; assigning to the flow a special identifier capable of identifying a relaying target routing processing device of the flow; reading out each message from the message buffer, assigning the special identifier to each message, and transmitting each message to a default communication channel which is formed such that each one of a plurality of connection target routing processing devices judges whether or not to receive each message arrived from the default communication channel according to the special identifier; setting up a bypass communication channel through which each message will be transferred to the relaying target routing processing device, when the message buffer becomes a prescribed state; and switching a transmission target of each message read out from the message buffer from the default communication channel to the bypass communication channel, when the bypass communication channel is set up.
According to another aspect of the present invention there is provided a message relay method for relaying a message from one routing processing device to another routing processing device among a plurality of routing processing devices for carrying out connection-less communications, the method comprising the steps of: entering a multicast connection set up request containing a multicast group address and information on a plurality of destination addresses corresponding to the multicast group address; notifying a set of the multicast group address and the destination addresses to each routing processing device which is a relaying target of a multicast connection, prior to transmission of messages, when messages destined to the multicast group address subsequently arrive from a default communication channel which is formed such that each one of a plurality of connection target routing processing devices judges whether or not to receive each message arrived from the default communication channel according to a value of a destination address region; collecting an information on an order relationship among relaying target routing processing devices on the multicast connection, in conjunction with a notification of the set of the multicast group address and the destination addresses; allocating a message buffer to messages destined to the multicast group address; storing messages destined to the multicast group address which are entered from one routing processing device into the message buffer; reading out each message from the message buffer, and transmitting each message to the default communication channel; setting up a bypass communication channel through which each message will be transferred to the relaying target routing processing devices according to the order relationship, when the message buffer becomes a prescribed state; and switching a transmission target of each message read out from the message buffer from the default communication channel to the bypass communication channel, when the bypass communication channel is set up.